package xj.graph2d.graph;

import java.awt.Point;
import java.awt.geom.Point2D;

import xj.graph2d.util.DrawingUtilities;
import xj.util.gui.Point2DFloat;

public class Geometry {

  public static double distance(Point p1, Point p2) {
    if (p1 != null && p2 != null) {
      return distance(p1.x, p1.y, p2.x, p2.y);
    } else {
      return Double.NaN;
    }
  }

  public static double distance(Point2D p1, Point2D p2) {
    if (p1 != null && p2 != null) {
      return distance(p1.getX(), p1.getY(), p2.getX(), p2.getY());
    } else {
      return Double.NaN;
    }
  }

  public static double distance(int x1, int y1, int x2, int y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  }

  public static double distance(double x1, double y1, double x2, double y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  }

  // intersection of two lines [p11, p12] and [p21, p22] 
  public static Point intersection(Point p11, Point p12, 
				   Point p21, Point p22) {
    if (p11 != null && p12 != null && p21 != null && p22 != null) {
      Point2D p = intersection(p11.x, p11.y, p12.x, p12.y, 
			       p21.x, p21.y, p22.x, p22.y);
      if (p != null) {
	return new Point((int) p.getX(), (int) p.getY());
      }
    }
    return null;
  }

  // intersection of two lines [p11, p12] and [p21, p22] 
  public static Point2D intersection(Point2D p11, Point2D p12, 
				     Point2D p21, Point2D p22) {
    if (p11 != null && p12 != null && p21 != null && p22 != null) {
      return intersection(p11.getX(), p11.getY(), p12.getX(), p12.getY(), 
			  p21.getX(), p21.getY(), p22.getX(), p22.getY());
    } else {
      return null;
    }
  }

  // intersection of two lines [(x11,y11), (x12,y12)] and [(x21,y21), (x22,y22)] 
  public static Point2D intersection(double x11, double y11, double x12, double y12, 
				     double x21, double y21, double x22, double y22) {
    double t1 = (y12 - y11) / (x12 - x11);
    double t2 = (y22 - y21) / (x22 - x21);

    if (eq(x11, x12)) {
      double y = t2 * (x11 - x21) + y21;
      return new Point2DFloat((float) x11, (float) y);
    }
    if (eq(y11, y12)) {
      double x = (y11 - y21) / t2 + x21;
      return new Point2DFloat((float) x, (float) y11);
    }

    if (eq(x21, x22)) {
      double y = t1 * (x21 - x11) + y11;
      return new Point2DFloat((float) x21, (float) y);
    }
    if (eq(y21, y22)) {
      double x = (y21 - y11) / t1 + x11;
      return new Point2DFloat((float) x, (float) y21);
    }

    if (Math.abs(t1 - t2) < 0.000001) {
      return null;
    }

    double a1 = t1;
    double b1 = -1.0;
    double c1 = t1 * x11 - y11;
    double a2 = t2;
    double b2 = -1.0;
    double c2 = t2 * x21 - y21;
    double D = a1 * b2 - a2 * b1;
    double Dx = c1 * b2 - c2 * b1;
    double Dy = a1 * c2 - a2 * c1;
    double x = Dx / D;
    double y = Dy / D;
    Point2D p = new Point2DFloat((float) x, (float) y);
    //CHECK(p);
    return p;
  }

  // if p is inside the box defined by corners [p1, p2] 
  public static boolean inBox(Point p, Point p1, Point p2) {
    if (p != null && p1 != null && p2 != null) {
      return inBox(p.x, p.y, p1.x, p1.y, p2.x, p2.y);
    } else {
      return false;
    }
  }

  // if p is inside the box defined by corners [p1, p2] 
  public static boolean inBox(Point2D p, Point2D p1, Point2D p2) {
    if (p != null && p1 != null && p2 != null) {
      return inBox(p.getX(), p.getY(), p1.getX(), p1.getY(), p2.getX(), p2.getY());
    } else {
      return false;
    }
  }

  // if point (x,y) is inside the box defined by corners [(x1,y1), (x2,y2)] 
  public static boolean inBox(double x, double y, 
			      double x1, double y1,
			      double x2, double y2) {
    double xmin = Math.min(x1, x2) - 1;
    double xmax = Math.max(x1, x2) + 1;
    double ymin = Math.min(y1, y2) - 1;
    double ymax = Math.max(y1, y2) + 1;
    return (x >= xmin && x <= xmax && y >= ymin && y <= ymax);
  }

  // intersection of two line segments [p11, p12] and [p21, p22] 
  public static Point intersectionWithin(Point p11, Point p12, 
					 Point p21, Point p22) {
    if (p11 != null && p12 != null && p21 != null && p22 != null) {
      Point2D p = intersectionWithin(p11.x, p11.y, p12.x, p12.y, 
				     p21.x, p21.y, p22.x, p22.y);
      if (p != null) {
	return new Point((int) p.getX(), (int) p.getY());
      }
    }
    return null;
  }

  // intersection of two line segments [p11, p12] and [p21, p22] 
  public static Point2D intersectionWithin(Point2D p11, Point2D p12,
					   Point2D p21, Point2D p22) {
    if (p11 != null && p12 != null && p21 != null && p22 != null) {
      return intersectionWithin(p11.getX(), p11.getY(), p12.getX(), p12.getY(),
				p21.getX(), p21.getY(), p22.getX(), p22.getY());
    } else {
      return null;
    }
  }

  // intersection of two line segments [(x11,y11), (x12,y12)] and [(x21,y21), (x22,y22)] 
  public static Point2D intersectionWithin(double x11, double y11, double x12, double y12, 
					   double x21, double y21, double x22, double y22) {
    Point2D p = intersection(x11, y11, x12, y12, x21, y21, x22, y22);
    if (p != null && 
	inBox(p.getX(), p.getY(), x11, y11, x12, y12) && 
	inBox(p.getX(), p.getY(), x21, y21, x22, y22)) {
      return p;
    } else {
      return null;
    }
  }

  public static Point2D intersectionWithinRect(double x11, double y11, double x12, double y12, 
					       double x21, double y21, double x22, double y22) {
    Point2D p = intersection(x11, y11, x12, y12, x21, y21, x22, y22);
    if (p != null && 
	inBox(p.getX(), p.getY(), x11, y11, x12, y12)) {
      return p;
    } else {
      return null;
    }
  }

  // intersection of line [lp1, lp2] and the rectagle defined by corners [rp1, rp2] 
  public static Point intersectionRectLine(Point rp1, Point rp2, 
					   Point lp1, Point lp2) {
    if (rp1 != null && rp2 != null && lp1 != null && lp2 != null) {
      Point2D p = intersectionRectLine(rp1.x, rp1.y, rp2.x, rp2.y, lp1.x, lp1.y, lp2.x, lp2.y);
      if (p != null) {
	return new Point((int) p.getX(), (int) p.getY());
      }
    }
    return null;
  }

  // intersection of line [lp1, lp2] and the rectagle defined by corners [rp1, rp2] 
  public static Point2D intersectionRectLine(Point2D rp1, Point2D rp2,
					     Point2D lp1, Point2D lp2) {
    if (rp1 != null && rp2 != null && lp1 != null && lp2 != null) {
      return intersectionRectLine(rp1.getX(), rp1.getY(), rp2.getX(), rp2.getY(), 
				  lp1.getX(), lp1.getY(), lp2.getX(), lp2.getY());
    } else {
      return null;
    }
  }

  // intersection of line [(lx1,ly1), (lx2,ly2)] and 
  // the rectagle defined by corners [(rx1,ry1), (rx2,ry2)] 
  // return the intersection closer to (lx1, ly1)
  public static Point2D intersectionRectLine(double rx1, double ry1, double rx2, double ry2, 
					     double lx1, double ly1, double lx2, double ly2) {
    Point2D p;
    Point2D p0 = null;
    double d0 = 0, d1;

    /*
    // check special cases: one of the point on the edge of the rectangle  
    if (eq(lx1, rx1) || eq(lx1, rx2) || eq(ly1, ry1) || eq(ly1, ry2)) { 
      return new Point2DFloat((float) lx1, (float) ly1);
    }
    if (eq(lx2, rx1) || eq(lx2, rx2) || eq(ly2, ry1) || eq(ly2, ry2)) { 
      return new Point2DFloat((float) lx2, (float) ly2);
    }
    */

    // intersect with the rectangle edges
    p = intersectionWithin(rx1, ry1, rx2, ry1, lx1, ly1, lx2, ly2);
    if (p != null) {
      p0 = p;
      d0 = distance(p.getX(), p.getY(), lx1, ly1);
    }
    p = intersectionWithin(rx1, ry2, rx2, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    p = intersectionWithin(rx1, ry1, rx1, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    p = intersectionWithin(rx2, ry1, rx2, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    if (p0 != null) { 
      //CHECK(p0);
      return p0;
    }

    // intersect with extended line
    p = intersectionWithinRect(rx1, ry1, rx2, ry1, lx1, ly1, lx2, ly2);
    if (p != null) {
      p0 = p;
      d0 = distance(p.getX(), p.getY(), lx1, ly1);
    }
    p = intersectionWithinRect(rx1, ry2, rx2, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    p = intersectionWithinRect(rx1, ry1, rx1, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    p = intersectionWithinRect(rx2, ry1, rx2, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }

    /*
    if (p0 != null) {
      return p0;
    }

    // intersect with extended line
    p = intersection(rx1, ry1, rx2, ry1, lx1, ly1, lx2, ly2);
    if (p != null) {
      p0 = p;
      d0 = distance(p.getX(), p.getY(), lx1, ly1);
    }
    p = intersection(rx1, ry2, rx2, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    p = intersection(rx1, ry1, rx1, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    p = intersection(rx2, ry1, rx2, ry2, lx1, ly1, lx2, ly2);
    if (p != null) {
      d1 = distance(p.getX(), p.getY(), lx1, ly1);
      if (p0 == null || d1 < d0) {
	p0 = p;
	d0 = d1;
      }
    }
    */
    
    //CHECK(p0);
    return p0;
  }

  /**
   * If the point (px, py) is inside the ellipse defined by two opposite corners: 
   * (ex1, ey1) and (ex2, ey2) 
   */
  public static boolean inEllipse(float ex1, float ey1, float ex2, float ey2, 
				  float px, float py) { 
    float cx = (ex1 + ex2) / 2;
    float cy = (ey1 + ey2) / 2;
    float a = Math.abs(ex1 - ex2) / 2;
    float b = Math.abs(ey1 - ey2) / 2;
    float pxc = px - cx;
    float pyc = py - cy;

    return (((pxc * pxc) / (a * a) + (pyc * pyc) / (b * b)) <= 1);
  }

  public static boolean inEllipse(Point2D ep1, Point2D ep2, Point2D p) {
    if (ep1 != null && ep2 != null && p != null) {
      return inEllipse((float) ep1.getX(), (float) ep1.getY(),
		       (float) ep2.getX(), (float) ep2.getY(), 
		       (float) p.getX(), (float) p.getY());
    } 
    return false;
  }

  public static Point2D intersectionEllipseLine(Point2D ep1, Point2D ep2, Point2D lp) {
    if (ep1 != null && ep2 != null && lp != null) {
      return intersectionEllipseLine((float) ep1.getX(), (float) ep1.getY(),
				     (float) ep2.getX(), (float) ep2.getY(), 
				     (float) lp.getX(), (float) lp.getY());
    } else {
      return null;
    }
  }

  public static Point2D intersectionEllipseLine(Point2D ep1, Point2D ep2,
						Point2D lp1, Point2D lp2) {
    if (ep1 != null && ep2 != null && lp1 != null && lp2 != null) {
      return intersectionEllipseLine((float) ep1.getX(), (float) ep1.getY(),
				     (float) ep2.getX(), (float) ep2.getY(), 
				     (float) lp1.getX(), (float) lp1.getY(), 
				     (float) lp2.getX(), (float) lp2.getY());
    } else {
      return null;
    }
  }

  /**
   * Intersection between a line and an ellipse. The ellipse is defined by
   * two opposite corners: (ex1, ey1) and (ex2, ey2) The line is defined
   * by (lx, ly) and the center of the ellipse. Find the intersection
   * closer to (lx, ly).
   */
  public static Point2D intersectionEllipseLine(float ex1, float ey1, float ex2, float ey2, 
						float lx, float ly) {
    float cx = (ex1 + ex2) / 2;
    float cy = (ey1 + ey2) / 2;
    float a = Math.abs(ex1 - ex2) / 2;
    float b = Math.abs(ey1 - ey2) / 2;
    float t = (float) DrawingUtilities.calculateRotationAngle(cx, cy, lx, ly);
    float x = cx + a * (float) Math.cos(t);
    float y = cy + b * (float) Math.sin(t);
    Point2D p = new Point2DFloat(x, y);
    //CHECK(p);
    return p;
  }

  public static final int DEFAULT_MODE = 0;

  public static final int ANY_QUADRANT = 0;

  public static final int UPPER_RIGHT_QUADRANT = 1;

  public static final int UPPER_LEFT_QUADRANT = 2;

  public static final int LOWER_LEFT_QUADRANT = 3;

  public static final int LOWER_RIGHT_QUADRANT = 4;

  /**
   * Intersection between a line and an ellipse. The ellipse is defined by
   * two opposite corners: (ex1, ey1) and (ex2, ey2) The line is defined
   * by (lx1, ly1) and (lx2, ly2). The second point (lx2, ly2) is inside
   * the ellipse. Find the intersection closer to the first point (lx1,
   * ly2).
   */
  public static Point2D intersectionEllipseLine(float ex1, float ey1, float ex2, float ey2, 
						float lx1, float ly1, float lx2, float ly2) {
    return intersectionEllipseLine(ex1, ey1, ex2, ey2, lx1, ly1, lx2, ly2, ANY_QUADRANT);
  }

  /**
   * Intersection between a line and an ellipse. The ellipse is defined by
   * two opposite corners: (ex1, ey1) and (ex2, ey2) The line is defined
   * by (lx1, ly1) and (lx2, ly2). The second point (lx2, ly2) is inside
   * the ellipse. Find the intersection closer to the first point (lx1,
   * ly1) and in the specified quadrant.
   */
  public static Point2D intersectionEllipseLine(float ex1, float ey1, float ex2, float ey2, 
						float lx1, float ly1, float lx2, float ly2,
						int quadrant) {
    /*
      Solution: 
      1. Center and axis of the ellipse 
         float cx = (ex1 + ex2) / 2; 
	 float cy = (ey1 + ey2) / 2; 
	 float a = Math.abs(ex1 - ex2) / 2;
         float b = Math.abs(ey1 - ey2) / 2;
          
     2. Shift the coordinates to the center of the ellipse 
        ex1c = ex1 - cx; 
	ey1c = ey1 - cy; 
	ex2c = ex2 - cx; 
	ey2c = ey2 - cy; 
	lx1c = lx1 - cx;
	ly1c = ly1 - cy; 
	lx2c = lx2 - cx; 
	ly2c = ly2 - cy;
          
     3. The equations: 
        (3.1) x^2 / a^2 + y^2 / b^2 == 1; 
	(3.2) (y - ly2c) / (x - lx2c) == (ly1c - ly2c) / (lx1c - lx2c);
         
     4. From (3.2) (3.1) 
        y == k * x + d, 
	  where k = (ly1c - ly2c) / (lx1c - lx2c); 
	d = - k * lx2c + ly2c;
         
     5. Plug into (3.1) 
        x^2 / a^2 + (k*x + d)^2 / b^2 - 1 == 0; 
	(5.1) A* x^2 + B * x + C == 0; 
	   where A = 1/a^2 + k^2/b^2; B = 2 * k * d / b^2; C = d^2 / b^2 - 1;
         
     6. Solve (5.1) 
        x1 = (-B + sqrt(B^2 - 4 * A * C)) / (2 * A) 
	x2 = (-B - sqrt(B^2 - 4 * A * C)) / (2 * A)         
    */

    float cx = (ex1 + ex2) / 2;
    float cy = (ey1 + ey2) / 2;

    if (!inEllipse(ex1, ey1, ex2, ey2, lx2, ly2)) { 
      lx2 = cx;
      ly2 = cy;
      //return null;
    }

    float x, y;

    if (eq(lx1, lx2) && eq(ly1, ly2)) {
      return new Point2DFloat(lx1, ly1);
    }

    float a = Math.abs(ex1 - ex2) / 2;
    float b = Math.abs(ey1 - ey2) / 2;

    float lx1c = lx1 - cx;
    float ly1c = ly1 - cy;
    float lx2c = lx2 - cx;
    float ly2c = ly2 - cy;

    if (eq(lx1c, 0) && eq(lx2c, 0)) {
      x = 0;
      if (ly1c != 0) { 
	if (ly1c > 0) {
	  y = b;
	} else {
	  y = -b;
	}
      } else { 
	if (ly2c > 0) {
	  y = b;
	} else { 
	  y = -b;
	}
      }
      return new Point2DFloat(x + cx, y + cy);
    }

    float a2 = a * a;
    float b2 = b * b;

    if (eq(lx1c, lx2c)) {
      x = lx1c;
      y = (float) Math.sqrt((1 - x * x / a2) * b2);
      if (ly2c < 0) {
	y = -y;
      }
      return new Point2DFloat(x + cx, y + cy);
    }

    float k = (ly1c - ly2c) / (lx1c - lx2c);
    float d = -k * lx2c + ly2c;
    float A = 1 / a2 + k * k / b2;
    float B = 2 * k * d / b2;
    float C = d * d / b2 - 1;
    float d0 = (B * B - 4 * A * C); 
    float D = (float) Math.sqrt(d0);


    if (d0 < 0) { 
      //throw new RuntimeException("Negative " + d0);

      System.err.println("Geometry.intersectionEllipseLine(): Negative " + d0);
      return null;
    }

    //CHECK(k);
    //CHECK(A);
    //CHECK(B);
    //CHECK(C);
    //CHECK(D);

    float x1 = (-B + D) / (2 * A);
    float x2 = (-B - D) / (2 * A);
    float y1 = k * x1 + d;
    float y2 = k * x2 + d;
    boolean in1 = inQuadrant(x1, y1, quadrant);
    boolean in2 = inQuadrant(x2, y2, quadrant);

    if (in1 && in2 || !in1 && !in2) {
      double d1 = distance(lx1c, ly1c, x1, y1);
      double d2 = distance(lx1c, ly1c, x2, y2);
      if (d1 <= d2) {
	x = x1;
	y = y1;
      } else {
	x = x2;
	y = y2;
      }
    } else if (in1 && !in2) {
      x = x1;
      y = y1;
    } else if (!in1 && in2) {
      x = x2;
      y = y2;
    } else {
      // shouldn't happen
      x = x1;
      y = y1;
    }
    Point2D p = new Point2DFloat(x + cx, y + cy);
    //CHECK(p);
    return p;
  }

  public static boolean inQuadrant(Point2D p, int quadrant) {
    if (p != null) {
      double x = p.getX();
      double y = p.getY();
      return inQuadrant(x, y, quadrant);
    }
    return false;
  }

  public static boolean inQuadrant(double x, double y, int quadrant) {
    if (quadrant == ANY_QUADRANT) {
      return true;
    } else {
      int sx = 0, sy = 0;
      switch (quadrant) {
      case UPPER_RIGHT_QUADRANT:
	sx = 1;
	sy = 1;
	break;
      case UPPER_LEFT_QUADRANT:
	sx = -1;
	sy = 1;
	break;
      case LOWER_LEFT_QUADRANT:
	sx = -1;
	sy = -1;
	break;
      case LOWER_RIGHT_QUADRANT:
	sx = 1;
	sy = -1;
	break;
      }
      return (sign(x) == sx && sign(y) == sy);
    }
  }

  public static int sign(double v) {
    if (v == 0.0) {
      return 0;
    } else if (v > 0.0) {
      return 1;
    } else {
      return -1;
    }
  }

  public static boolean eq(double d1, double d2) {
    return (Math.abs(d1 - d2) < 0.000001);
  }

  public static Point2D intersectionPolygonLine(Point2D[] points, 
						Point2D lp1, Point2D lp2) {
    if (points != null && lp1 != null && lp2 != null) {
      return intersectionPolygonLine(points, points.length, lp1, lp2);
    }
    return null;
  }

  public static Point2D intersectionPolygonLine(Point2D[] points, int n,
						Point2D lp1, Point2D lp2) {
    if (points != null && 
	n <= points.length && 
	lp1 != null && lp2 != null) {
      double lx1 = lp1.getX();
      double ly1 = lp1.getY();
      double lx2 = lp2.getX();
      double ly2 = lp2.getY();
      double x1, y1, x2, y2;
      Point2D p;
      for (int i = 1; i < n; i++) {
	if (points[i - 1] != null && points[i] != null) {
	  x1 = points[i - 1].getX();
	  y1 = points[i - 1].getY();
	  x2 = points[i].getX();
	  y2 = points[i].getY();
	  p = intersectionWithin(x1, y1, x2, y2, lx1, ly1, lx2, ly2);
	  if (p != null) {
	    return p;
	  }
	}
      }
      if (points[n - 1] != null && points[0] != null) {
	x1 = points[n - 1].getX();
	y1 = points[n - 1].getY();
	x2 = points[0].getX();
	y2 = points[0].getY();
	p = intersectionWithin(x1, y1, x2, y2, lx1, ly1, lx2, ly2);
	if (p != null) {
	  return p;
	}
      }

      // intersect with extended line
      Point2D p0 = null;
      double d0 = 0, d1;
      for (int i = 1; i < n; i++) {
	if (points[i - 1] != null && points[i] != null) {
	  x1 = points[i - 1].getX();
	  y1 = points[i - 1].getY();
	  x2 = points[i].getX();
	  y2 = points[i].getY();
	  p = intersectionWithinRect(x1, y1, x2, y2, lx1, ly1, lx2, ly2);
	  if (p != null) {
	    d1 = distance(p.getX(), p.getY(), lx1, ly1);
	    if (p0 == null || d1 < d0) {
	      p0 = p;
	      d0 = d1;
	    }
	  }
	}
      }
      if (points[n - 1] != null && points[0] != null) {
	x1 = points[n - 1].getX();
	y1 = points[n - 1].getY();
	x2 = points[0].getX();
	y2 = points[0].getY();
	p = intersectionWithinRect(x1, y1, x2, y2, lx1, ly1, lx2, ly2);
	if (p != null) {
	  d1 = distance(p.getX(), p.getY(), lx1, ly1);
	  if (p0 == null || d1 < d0) {
	    p0 = p;
	    d0 = d1;
	  }
	}
      }
      if (p0 != null) {
	return p0;
      }

      // intersect with extended line
      for (int i = 1; i < n; i++) {
	if (points[i - 1] != null && points[i] != null) {
	  x1 = points[i - 1].getX();
	  y1 = points[i - 1].getY();
	  x2 = points[i].getX();
	  y2 = points[i].getY();
	  p = intersection(x1, y1, x2, y2, lx1, ly1, lx2, ly2);
	  if (p != null) {
	    d1 = distance(p.getX(), p.getY(), lx1, ly1);
	    if (p0 == null || d1 < d0) {
	      p0 = p;
	      d0 = d1;
	    }
	  }
	}
      }
      if (points[n - 1] != null && points[0] != null) {
	x1 = points[n - 1].getX();
	y1 = points[n - 1].getY();
	x2 = points[0].getX();
	y2 = points[0].getY();
	p = intersection(x1, y1, x2, y2, lx1, ly1, lx2, ly2);
	if (p != null) {
	  d1 = distance(p.getX(), p.getY(), lx1, ly1);
	  if (p0 == null || d1 < d0) {
	    p0 = p;
	    d0 = d1;
	  }
	}
      }
      return p0;
    }
    return null;
  }

  //
  // Utilities for scaling points on the polyline/polycurve and curves
  // Objective, keep point in the same location relative to the two end points
  //
  public static Point2D scaleRelativeToEndPoints(Point2D p1, Point2D p2, // original pos of end points  
						 Point2D q1, Point2D q2, // new pos of end points  
						 Point2D r) {            // point to be scaled 
    if (p1 != null && p2 != null && q1 != null && q2 != null && r!= null) { 
      double d1 = distance(p1, p2);
      double d2 = distance(q1, q2);
      if (!eq(d1, 0) && !eq(d2, 0)) { 
	double a1 = angle(p1, p2); 
	double a2 = angle(q1, q2); 

	double d3 = distance(p1, r);
	//Point2D r2 = new Point2DFloat((float) (r.getX() - p1.getX()), (float) (r.getY() - p1.getY()));
	double a3 = angle(p1, r); 

	double d4 = d3 * d2 / d1; 
	double a4 = a3 - a1 + a2; 
	double x = q1.getX() + d4 * Math.cos(a4); 
	double y = q1.getY() + d4 * Math.sin(a4); 
	return new Point2DFloat((float) x, (float) y);
      } else {
	return q1;
      }
    }
    return r;
  }

  // return the angle between the line formed by (p1, p2) and the x-axis
  public static double angle(Point2D p1, Point2D p2) { 
    if (p1 != null && p2 != null) { 
      double dx = p2.getX() - p1.getX();
      double dy = p2.getY() - p1.getY();
      return Math.atan2(dy, dx);
    }
    return 0;
  }

  public static void CHECK(double d) { 
    if (Double.isNaN(d)) {
      throw new RuntimeException("Encountered NaN " + d);
    }
  }

  public static void CHECK(Point2D p) { 
    if (p != null) { 
      if (Double.isNaN(p.getX()) || Double.isNaN(p.getY())) { 
	throw new RuntimeException("Encountered NaN " + p);
      }
    }
  }

}
